package 组合问题.电话号码的字母组合;

import java.util.*;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 电话号码的字母组合
 * 此题是两个多个集合开始取元素，所以没有 startIndex,for循环应该从0开始，
 * 而不是startIndex开始，如果是一个集合取元素(且不能重复)，组合，则应该从startIndex 开始
 * @date 2022/11/13 15:21
 */
public class Demo17 {
    public static void main(String[] args) {
        List<String> strings = letterCombinations("23");
        System.out.println(strings);
    }
    static HashMap<Character,String> hashMap=new HashMap<>();
     static List<String>  res=new ArrayList<>();
    static LinkedList<Character>  path=new LinkedList<>();
    public static List<String> letterCombinations(String digits) {
        if(digits==null||"".equals(digits)){
            return res;
        }
        hashMap.put('2',"abc");
        hashMap.put('3',"def");
        hashMap.put('4',"ghi");
        hashMap.put('5',"jkl");
        hashMap.put('6',"mno");
        hashMap.put('7',"pqrs");
        hashMap.put('8',"tuv");
        hashMap.put('9',"wzxy");
        backTrack(digits,0);
        return res;
    }

    private static void backTrack(String digits, int index) {
        if(path.size()==digits.length()){
            StringBuilder s=new StringBuilder();
            for (int i = 0; i < path.size(); i++) {
                s.append( path.get(i));
            }
            res.add(s.toString());
            return;
        }
        for (int j =0; j <hashMap.get(digits.charAt(index)).length(); j++) {
            path.add(hashMap.get(digits.charAt(index)).charAt(j));
            backTrack(digits,index+1);
            path.removeLast();
        }
    }
}
